let arrOri = [];
if (arrOri.length == 0) {
    for (let i = 0; i < 50; i++){
        arrOri.push(Math.ceil(100 * Math.random()));
    }
    console.log("oriArr:", arrOri.toString());
}

function copyArr(arr, b, n) {
    let copy_arr = [];
    b = b || 0;
    n = n === undefined ? arr.length : n;
    for (let i = b; i < n; i++){
        copy_arr.push(arr[i]);
    }
    return copy_arr;
}


function bubbleSort(arr) {    
    for (let i = 0; i < arr.length; i++){
        let len = arr.length - i - 1;
        for (let j = 0; j < len; j++){
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr.toString();
}
console.log("bubble:", bubbleSort(copyArr(arrOri)));

function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++){
        let minIdx = i;
        for (let j = i + 1; j < arr.length; j++){
            if (arr[minIdx] > arr[j]) {
                minIdx = j;
            }
        }
        if (minIdx != i) {
            let temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
    return arr.toString();
}
console.log("select:", selectionSort(copyArr(arrOri)));

function insertionSort(arr) {
    let cur = NaN;
    for (let i = 1; i < arr.length; i++){
        cur = arr[i];
        let preIdx = i - 1;
        while (preIdx >= 0 && cur < arr[preIdx]) {
            arr[preIdx + 1] = arr[preIdx];
            preIdx--;
        }
        arr[preIdx + 1] = cur;
    }
    return arr.toString();
}
console.log("insert:", insertionSort(copyArr(arrOri)));

function shellSort(arr) {
    let len = arr.length;
    let temp = NaN;
    let gap = Math.floor(len / 2);
    while (gap > 0) {
        for (let i = gap; i < len; i++){
            cur = arr[i];
            let preIdx = i - gap;
            while (preIdx >= 0 && cur < arr[preIdx]) {
                arr[preIdx + gap] = arr[preIdx];
                preIdx -= gap;
            }
            arr[preIdx + gap] = cur;
        }
        gap = Math.floor(gap / 2);
    }
    return arr.toString();
}
console.log("shell :", shellSort(copyArr(arrOri)));

function mergeSort(arr) {
    let merge = (left, right) => { 
        let result = [];
        let len = left.length + right.length;
        let index = 0; i = 0; j = 0;
        for (; index < len; index++){
            if (i >= left.length) {
                result[index] = right[j++];
            } else if (j >= right.length) {
                result[index] = left[i++];
            } else if (left[i] > right[j]) {
                result[index] = right[j++];
            } else {
                result[index] = left[i++];
            }
        }
        return result;
    };
    let sort = (a) => {
        if (a.length < 2) return a;        
        let mid = Math.floor(a.length / 2);
        let left = copyArr(a, 0, mid);
        let right = copyArr(a, mid, a.length);
        return merge(sort(left), sort(right));
    };

    let newArr = sort(arr);
    return newArr.toString();
}
console.log("merge :", mergeSort(copyArr(arrOri)));

function quickSort(arr) {
    let swap = (a, i, j) => {
        let temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    };
    let partition = (a, start, end) => {        
        let pivot = Math.floor((start + end) / 2);
        let smallIndex = start - 1;
        swap(a, pivot, end);
        for (let i = start; i <= end; i++){
            if (a[i] <= a[end]) {
                smallIndex++;
                if (i > smallIndex) {
                    swap(a, i, smallIndex);
                }
            }
        }
        return smallIndex;
    };    
    let sort = (a, start, end) => {
        if (a.length < 1 || start < 0 || end >= a.length || start >= end) {
            return;
        }
        let smallIndex = partition(a, start, end);
        if (smallIndex > start) {
            sort(a, start, smallIndex - 1);
        }
        if (smallIndex < end) {
            sort(a, smallIndex + 1, end);
        }
    };

    sort(arr, 0, arr.length - 1);
    return arr.toString();
}
console.log("quick :", quickSort(copyArr(arrOri)));

function heapSort(arr) {
    var len = arr.length;
    let swap = (a, i, j) => {
        let temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    };
    let adjustHeap = (a, i) => {
        let maxIndex = i;
        if (i * 2 + 1 < len && a[i * 2 + 1] > a[maxIndex]) {
            maxIndex = i * 2 + 1;
        }
        if (i * 2 + 2< len && a[i * 2 + 2] > a[maxIndex]) {
            maxIndex = i * 2 + 2;
        }
        if (maxIndex != i) {
            swap(a, maxIndex, i);
            adjustHeap(a, maxIndex);
        }
    };
    let buildMaxHeap = (a) => {
        let i = Math.floor(len / 2) - 1;
        for (; i >= 0; i--){
            adjustHeap(a, i);
        }
    };

    buildMaxHeap(arr);
    while (len > 0) {
        swap(arr, 0, len - 1);
        len--;
        adjustHeap(arr, 0);
    }
    return arr.toString();
}
console.log("heap  :", heapSort(copyArr(arrOri)));

function countingSort(arr) {
    // arr must int arr
    let min = arr[0], max = arr[0];
    for (let i = 0; i < arr.length; i++){
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    let bias = 0 - min;
    let bucket = [];
    for (let i = 0; i < arr.length; i++){
        let idx = arr[i] + bias;
        if (!bucket[idx]) {
            bucket[idx] = 0;
        }
        bucket[idx]++;
    }
    let index = 0, i = 0;
    while (index < arr.length) {
        if (bucket[i]) {
            arr[index] = i - bias;
            bucket[i]--;
            index++;
        } else {
            i++;
        }
    }
    return arr.toString();
}
console.log("count :", countingSort(copyArr(arrOri)));